This Phase I, multicenter, randomized, placebo-controlled, double-blind trial will evaluate the safety and immunogenicity of the prime-boost immunization approach in vaccinia-naive and vaccinia-immune individuals using a novel recombinant vaccine vector expressing HIV-1 envelope, and poly gene products and subsequently will address questions pertaining to the optimal boosting strategy raised by the previous trials of vaccinia recombinant expressing gp160 alone.